package leetcode

import "sort"

// 测试链接 : https://leetcode.cn/problems/set-intersection-size-at-least-two/

// intersectionSizeTwo 计算具有至少两个交点的最小数组的大小。
// intervals 是一个二维整数数组，每个子数组表示一个区间。
func intersectionSizeTwo(intervals [][]int) int {
	// 对区间进行排序，首先根据结束数字升序排序，
	// 如果结束数字相同，则根据开始数字降序排序。
	// 这样排序的目的是为了在遍历时，能够更容易地判断
	// 当前区间是否与已选择的区间有交集。
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][1] != intervals[j][1] {
			return intervals[i][1] < intervals[j][1]
		} else {
			return intervals[j][0] < intervals[i][0]
		}
	})

	n := len(intervals)
	// 初始化pos为第一个区间的结束数字，
	// 初始化pre为第一个区间的倒数第二个数字。
	pos := intervals[0][1]
	pre := pos - 1
	// ans初始化为2，因为第一个区间必定需要选择两个数字。
	ans := 2

	// 从第二个区间开始遍历，判断每个区间是否需要额外选择数字以确保交集要求。
	for i := 1; i < n; i++ {
		// 如果当前区间的开始数字大于pre，则说明当前区间与已选择的区间
		// 不满足交集要求，需要额外选择数字。
		if intervals[i][0] > pre {
			if intervals[i][0] > pos {
				// 如果当前区间的开始数字大于pos，说明需要选择两个新的数字。
				pre = intervals[i][1] - 1
				ans += 2
			} else {
				// 如果当前区间的开始数字不大于pos，说明只需要选择一个新数字。
				pre = pos
				ans += 1
			}
			// 更新pos为当前区间的结束数字。
			pos = intervals[i][1]
		}
	}
	// 返回选择数字的总数。
	return ans
}
